#include <bits/stdc++.h>
using namespace std;
const int N=2002, M=10001;
int n, m, cnt=0;
struct Edge
{
	int v, w, next;
}edge[M*2];
//struct Node
//{
//	int id, dist;
//	bool operator < (const Node &x) const{
//		return x.dist < dist;
//	}
//};

struct Node
{
	int id, dist;
};
bool operator >(Node a, Node b)
{
	return a.dist>b.dist;
}

int head[N],d[N],p[N];
bool v[N];

void print(int s)
{
	if(p[s]!=0) print(p[s]);
	cout<<s<<" ";
}

void add_edge(int u, int v, int w)
{
	edge[++cnt].next=head[u];
	edge[cnt].v = v;
	edge[cnt].w = w;
	head[u]=cnt;
}

void dijkstra(int s)
{
	priority_queue<Node, vector<Node>, greater<Node> > pq;
	memset(d, 0x3f, sizeof(d));
	d[s]=0;
	Node tp, np;
	tp.id=s;
	tp.dist=0;
	pq.push(tp);
	while(!pq.empty())
	{
		tp=pq.top(); pq.pop();
		if(v[tp.id]) continue;
		int k=tp.id;
		v[k]=true;
		for(int e=head[k]; e; e=edge[e].next)
		{
			if(!v[edge[e].v] && d[k]+edge[e].w<d[edge[e].v])
			{
				d[edge[e].v] = d[k]+edge[e].w;
				p[edge[e].v] = k;
				np.id=edge[e].v;
				np.dist=d[edge[e].v];
				pq.push(np);
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	int u,v,w;
	for(int i=1;i<=m;++i)
	{
		cin>>u>>v>>w;
		add_edge(u,v,w);
		add_edge(v,u,w);
	}

	dijkstra(1);

	for(int i=1;i<=n;++i)
	{
		cout<<i<<"("<<d[i]<<") ";
		print(i);
		cout<<endl;
	}
	return 0;
}
